/**
 * 148. 排序链表
 * https://leetcode-cn.com/problems/sort-list/
 */
const { displayListNode, createListNode, ListNode } = require('../../libs/public');

/**
 * @param {ListNode} head1
 * @param {ListNode} head2
 * @return {ListNode}
 */
function merge(head1, head2) {
  let node1 = head1;
  let node2 = head2;
  let newHead;
  if (node1.val < node2.val) {
    newHead = node1;
    node1 = node1.next;
  } else {
    newHead = node2;
    node2 = node2.next;
  }
  let node = newHead;
  while (node1 && node2) {
    if (node1.val < node2.val) {
      node.next = node1;
      node1 = node1.next;
    } else {
      node.next = node2;
      node2 = node2.next;
    }
    node = node.next;
  }
  if (node1) {
    node.next = node1;
  } else if (node2) {
    node.next = node2;
  }
  return newHead;
}

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
function sortList(head) {
  if (!head) {
    return head;
  }
  let size = 0;
  let node = head;
  while (node) {
    size += 1;
    node = node.next;
  }
  const virtualHead = new ListNode(0);
  virtualHead.next = head;
  for (let subLength = 1; subLength < size; subLength *= 2) {
    let pre = virtualHead;
    while (pre.next) {
      const head1 = pre.next;
      node = head1;
      let tail1 = node;
      for (let i = 0; i < subLength && node; i += 1) {
        tail1 = node;
        node = node.next;
      }
      if (!node) {
        break;
      }
      pre.next = null;
      tail1.next = null;
      const head2 = node;
      let tail2 = node;
      for (let i = 0; i < subLength && node; i += 1) {
        tail2 = node;
        node = node.next;
      }
      const next = node;
      tail2.next = null;
      const newHead = merge(head1, head2);
      let newTail = newHead;
      while (newTail.next) {
        newTail = newTail.next;
      }
      newTail.next = next;
      pre.next = newHead;
      pre = newTail;
    }
  }
  const result = virtualHead.next;
  virtualHead.next = null;
  return result;
}

console.log(displayListNode(sortList(createListNode([4, 2, 1, 3]))) === '[1,2,3,4]');
console.log(displayListNode(sortList(createListNode([-1, 5, 3, 4, 0]))) === '[-1,0,3,4,5]');
console.log(displayListNode(sortList(createListNode([9, 8, 7, 6, 5, 4, 3, 2, 1, 0]))) === '[0,1,2,3,4,5,6,7,8,9]');
console.log(displayListNode(sortList(createListNode([]))) === '[]');
console.log(displayListNode(sortList(createListNode([1]))) === '[1]');
console.log(displayListNode(sortList(createListNode([2, 1]))) === '[1,2]');
console.log(displayListNode(sortList(createListNode([3, 2, 1]))) === '[1,2,3]');
